var knapsack = function (bagWeight, weight, value) {
  const n = weight.length;
  // base case 已初始化
  const dp = new Array(n + 1).fill().map(() => new Array(bagWeight + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= bagWeight; w++) {
      if (w - weight[i - 1] < 0) {
        // 这种情况下只能选择不装入背包
        dp[i][w] = dp[i - 1][w];
      } else {
        // 装入或者不装入背包，择优
        // 由于数组索引从 0 开始，而我们定义中的 i 是从 1 开始计数的，所以 value[i-1] 和 weight[i-1] 表示第 i 个物品的价值和重量
        dp[i][w] = Math.max(
          dp[i - 1][w - weight[i - 1]] + value[i - 1],
          dp[i - 1][w]
        );
      }
    }
  }

  return dp[n][bagWeight];
};

// test
console.log(knapsack(4, [1, 2, 3], [15, 20, 30])); // 45
console.log(knapsack(5, [2, 3, 4, 5], [1, 2, 5, 6])); // 6
console.log(knapsack(5, [1, 2, 3], [10, 15, 40])); // 55
